(1) Field of the Invention
The present invention relates to an error correcting method and, more particularly to, a technology for speedily solving an error-position polynomial for chien""s searching used in error correction.
(2) Description of the Related Art
Digital data written on a DVD-ROM and the like may produce a read-out error due to a fingerprint, other dirt, a scar, or the like if the data is read out as is. In order to cope with this, when data which is stored by use of a Reed-Solomon code is read out, an algorithm called chien""s searching is used to find an error position or error numeral for correction.
This is done so, because an odd/even parity check method which only adds one bit to every original seven data bits can find error generation itself but cannot specify error data nor find the generation itself in case two errors occur simultaneously, so that by providing a large number of parity bits in a duplicate manner, i.e. both horizontally and vertically, to thereby reduce a question of xe2x80x9ccorrecting an errorxe2x80x9d to a question of xe2x80x9csolving a simultaneous equation.xe2x80x9d The Reed-Solomon code itself is a known technology already described in, for example, xe2x80x9cINTRODUCTION TO CODE THEORYxe2x80x9d by Iwadare, published by Shouseidou, xe2x80x9cPRACTICAL ERROR CORRECTION TECHNOLOGYxe2x80x9d published by Trikeppsu, and the like. Also, arrays of data and parity bits on a DVD-ROM and the like and the ECC format are also already known. Therefore, detailed description on these issues is omitted here, and outlining only those items directly related to the present invention.
As shown in FIG. 1, 1 (one) ECC (error correction code) according to a DVD format comprises a rectangular-shaped data portion consisting of horizontal 172 bytes and vertical 182 bytes and additional two parity portions of a rightward 10-byte portion and a downward 16-byte portion.
With this, data read out from a DVD-ROM and the like is sent through a syndrome arithmetic unit, an Euclidean arithmetic unit and to a chien""s searching apparatus (error-position and numeral calculation unit).
In this configuration, the Euclidean arithmetic unit and the chien""s searching apparatus are provided for speeding, because an equation of interest cannot be solved if the number of employed parity bits is too large, such as 10 or 16.
In this configuration, the Euclidean arithmetic unit on the upstream side obtains an error-position polynomial L(X) and an error-numeral polynomial V(X) based on a syndrome polynomial S(X). In this case, a code polynomial C(X) uses d data pieces Di (i=0, 2, . . . , dxe2x88x921) and p parity bits Pi (i=0, . . . , pxe2x88x921) as coefficients in this order. Also, S(X) is obtained by substituting a root of a generation polynomial G(X) into a reception polynomial R(X) received. Note here that the parity bit of the code polynomial C(X) is added so that C(X) can be exactly divided by the generation polynomial G(X) having the parity bits as sequential coefficients. Also, the error-position polynomial L(X) is provided to obtain an error position Lj, while the error-numeral polynomial V(X) is provided to obtain an error numeral Ej.
With this, the error-position polynomial L(X) has X=xcex1{circumflex over ( )}xe2x88x92Lj(xe2x88x92Lj""th power of xcex1) as a solution. Further, a relation of Ej=xe2x88x92V(xcex1{circumflex over ( )}Lj)/Lodd(xcex1{circumflex over ( )}xe2x88x92Lj) holds. This mathematical expression is called an error-numeral polynomial. In this expression, the denominator Lodd is a function of only an odd-number order of the error-position polynomial L(X), while xcex1 is a root of the generation function C(X).
With this, X=xcex1{circumflex over ( )}0, xcex1{circumflex over ( )}1, xcex1{circumflex over ( )}2, . . . are substituted as a solution on a Galois field GF (2{circumflex over ( )}n; n""th power of 2) into an error-position polynomial L(X) obtained by the Euclidean algorithm, to thereby obtain a solution that a total sum of each bit component becomes 0. The Galois field and arithmetic operations thereon are known from disclosures in, for example, xe2x80x9cMODERNE ALGEBRAxe2x80x9d by B. L. van der Waerden, published by Springer Verlag, and the like, and a Galois field multiplier is also a so-called known technology, so that description on these issues is omitted here.
Note here that this error-position polynomial L(X) is expressed as follows if it has a maximum correction power p:
L(x)=ApX{circumflex over ( )}p+ . . . +A2x{circumflex over ( )}2+A1X{circumflex over ( )}1+A0
where A0-Ap are all coefficients of the 0""th power through the p""th power of X.
Such a circuit is called a chien""s searching (apparatus) that is constituted to solve this equation on a real-time basis, i.e. corresponding to a situation that one actually appreciates music or pictures, to thereby find an error position and obtain an error numeral. FIG. 2 shows the denominator of this chien""s searching apparatus, i.e. the calculation unit of the above mentioned L(xcex1{circumflex over ( )}xe2x88x92Lj).
In FIG. 2, a reference numeral 100 indicates an error-position calculating (also referred to as an error-position arithmetic) unit, i.e. the error-position polynomial calculating unit. Reference numerals 1010-101p indicate input terminals. Reference numerals 1020-102p indicate Galois field multipliers. Reference numerals 1030-103p indicate selectors (circuits). Reference numerals 1040-104p indicate registers or overwritable memories. A reference numeral 105 indicates a full adder (aggregate batcher). A reference numeral 106 indicates a 0-decoder. A reference numeral 107 indicates an odd-number order summing (aggregate) unit. A reference numeral 108 indicates an error-location counter. A reference numeral 109 indicates an error-location output signal terminal. A reference numeral 110 indicates an arithmetic-unit output-signal terminal. A reference numeral 111 indicates an even-number order sum output signal terminal.
With this, at the first cycle, each coefficient of an error-position polynomial is input from the Euclidean arithmetic unit (not shown) on the upstream side to their corresponding input terminals 1010-101p. The selectors 1030-103p following to each input terminal for each input terminals select a coefficient input from each of the input terminal 1010-101p at the beginning of only the initial cycle or at the start of the corresponding cycle and, during the subsequent cycle, always select as an input the output value from each of the Galois field multipliers 1020-102p, which is the other input signal. With this, according to the following procedure, xcex1{circumflex over ( )}0, xcex1{circumflex over ( )}1, xcex1{circumflex over ( )}2, . . . are sequentially substituted into X in the subsequent cycles, to thereby check one by one whether L(X)=0 or not.
Values selected by each of the selectors 1030-103p are respectively stored in the following registers 1040-104p in synchronization with a system clock signal, which values are then summed by the following full adder 105 at the beginning of the next cycle. This sum value is judged whether it is 0 or not by the 0-decoder 106. If it is judged as 0, j indicates an error position.
The reference numeral 108 indicates the error-location counter, which is reset to 0 at the first cycle and then counts up by one per every one clock cycle. That is, this error-location counter always stores a value of i+1 for every i cycles, so that its count value, when the o-decoder has judged as 0, indicates an error position.
In the cycle following the initial cycle, each value stored in each of the registers 1040-104p are respectively multiplied by xcex1{circumflex over ( )}0, xcex1{circumflex over ( )}1, . . . , xcex1{circumflex over ( )}p by the Galois field multipliers 1020-102p which branch from and follow the full adder 105, so that thus obtained products are respectively stored via the selectors 1030-103p newly in the registers 1040-104p in lace of the previous values.
A reference numeral 107 indicates an odd-number order full adder for summing only odd-number order terms in error polynomials. Thus obtained results are used in a divisor unit of the next-stage error-numeral polynomial arithmetic unit (not shown), to obtain an error numeral by utilizing the above mentioned relation.
Subsequently, this arithmetic operation to thereby decide the presence of an error and detect the error position.
Also, the error-location output terminal 109, the 0-decoder terminal 110, and the odd-number order sum output signal terminal 111 serve to provide their respective output signals to the arithmetic unit of the next-stage error-numeral polynomial.
FIG. 3 shows all the chien""s searching apparatus.
As shown in it, the chien""s searching apparatus comprises part of the error-position polynomial calculating unit 100 as shown in FIG. 2 and the denominator unit (denominator side arithmetic unit) consisting of the odd-number order summing unit 107 and the additional numerator unit (numerator side arithmetic unit) 300 and the error-numeral polynomial divisor unit (i.e., processing unit for the purpose of specifying an error position) 500, thus calculating an error numeral. In this configuration, the numerator unit 300 is provided for operating the above mentioned xe2x88x92V(xcex1{circumflex over ( )}xe2x88x92Lj), being different from the above mentioned error-position polynomial calculating unit 100 in the following four points:
1) In the initial cycle, there is present no p""th-order coefficient to be input;
2) Therefore, there is no Galois field multiplier present for this coefficient;
3) A different coefficient is to be input; and
4) There are no odd-number order summing unit nor 0-decoder.
With this, therefore, every element or component having the same actions as those in FIG. 2 has xe2x80x9c3xe2x80x9d in place of xe2x80x9c1xe2x80x9d as the initial number (top digit) of the reference numeral. Specifically, with the selectors, for example, since the error-position polynomial calculating units are given the reference numerals 1031-103p, the numerator units have reference numerals 3031-303p-1 (303p does not exist). Note here that a reference numeral 312 indicates an output signal terminal of the numerator units of the error-numeral polynomial and a reference numeral 514, an output signal terminal of the error-numeral polynomial divisor.
With this configuration, numerators of the above mentioned error-numeral polynomial are operated, to send thus obtained operation result to the error-numeral polynomial divisor 500. With this, the error-numeral polynomial divisor 500 uses this value as a numerator and an output signal terminal 111 of the odd-number order summing unit 107 of the error-position polynomial calculating unit 100 as a denominator, to thereby calculate an error numeral and place the result as an output.
With this further, subsequently, an error write-back device (not shown) rewrites data in a buffer memory as required, change a read-out speed, as required, for re-reading, changes an correction algorithm, and finally displays images on a CRT based on thus rewritten correct data. These technologies, however, are already known, so that their description on these issued is omitted here.
Improvements in recent years have increased the amount of data subject to error correction. This lead to needs for further speedy error correction processing for improvement in the reproduction speed of DVD-ROMs.
The above mentioned chien""s searching apparatus, however, can obtain only one solution by one-cycle time operations because of its error-position calculations. Its throughput, therefore, is determined by the one-cycle time lapse, a frequency of its clock signal, etc. If, to improve the throughput, the frequency of its driving clock signal is increased or the operational cycle time is decreased, however, the power dissipation is increased, the skew of the clock signal becomes difficult to adjust, the signal cannot easily swing full to thus permit hot carriers to cause reliability deterioration or signal propagation abnormality, adjustment is required with other equipment and circuits, or other problems may occur.
Similar problems would occur also with error-numeral calculations.
These problems led to need for the development of a technology that permits a chien""s searching apparatus to obtain solutions of an error-position polynomial speedily without increasing the cycle frequency.
Besides, because of the recent miniaturization and portability of various types of equipment using DVD-ROMs or otherwise, there have been strong desires for miniaturization and lower power dissipation of the various components. With this, in view of the above, there have been desires in the industries for the development of an appropriate chien""s searching apparatus.
Also, like in other technological fields, detailed study of the processing contents has found a possibility that they may contain unnecessary processing items. This led to a request for detailed review of the processing contents for further speeding in processing.
It is an object of the present invention to solve the above mentioned problems, actually taking notice of reducing an error rate. It is another object of the present invention to provide a plurality of arithmetic units to thereby speed arithmetic operations as well as miniaturize and reduce power dissipation of an apparatus. Specifically, the apparatus has the following configuration.
In the first aspect of the present invention, the so-called denominator side of a portion for error-position calculations in the apparatus which calculates an error position and an error numeral has in common for later described two error-position arithmetic units a plurality of input terminals for inputting the corresponding coefficients of an error-position polynomial, selecting portions (selectors), which corresponds to these coefficients, for selecting various values input at each input terminal at the beginning of only the initial cycle and, at the beginning of the subsequent cycles, those values input at the other input terminal, and a memory unit, which correspond to these coefficients, for storing (temporary memory) those values thus selected by these selecting portions by overwriting the previous values. It also has two arithmetic units corresponding to each of the coefficients, each of the two units comprising a Galois field multiplier, a full adder, a 0-decoder, an odd-number order summing unit, and an error-location counter.
With this, in the first cycle, the first error-position arithmetic unit on the downstream side and the second error-position arithmetic unit on the downstream side of the loop simultaneously perform the 2i""th power of xcex1(i=1, 2, . . . ) and the (2i+1)""th power of xcex1(i=0, 1, . . . ) respectively.
With this, also, the apparatus is so controlled that the error-location counter of the first error-position arithmetic unit is set at 0 at the first cycle and the error-location counter of the second error-position arithmetic unit is set at 1, for example, so that subsequently both of these error-location counters may count up by two for each cycle (xe2x80x9cfor examplexe2x80x9d here implies, as described later, that other configurations performing essentially the same actions may be included that comprises a first error-location counter which acts as a common error-location counter and a means for recognizing an error location value of the second Galois field multiplier unit based on the count value of the first error-location counter) and, further, for example, necessary wiring lines are connected between those units. Also, it is so controlled that arithmetic operations may be canceled when a necessary order number or a number of necessary cycles is attained or that each of the units may behave appropriately at their respective time points in each cycle in synchronization with the clock signal.
Specifically, for example, the output result of the first Galois field multiplier is held until the leading edge of the next clock cycle and, at the beginning of the next clock cycle, input immediately to the storage unit, based on which each process of the next cycle is performed.
Further, the apparatus is of course so controlled that since it has two Galois field multiplier units for simultaneously performing arithmetic operations of the (2i+1)""th power of xcex1 and the 2i""th power of xcex1, it as a rule has also two odd-number order summing unit and another two error-location counters unless in any special situation or device, thus enabling the downstream-side processing, for example, the outputting of a signal necessary for calculation of an error position.
According to a second aspect of the present invention, the chien""s searching apparatus comprises, for further speedy error-numeral calculation therein, two Galois field multipliers for each coefficient also for the portion for calculating a numerator, like in the case of the denominator, in error-numeral calculation. With this, similar to error-position calculation at the numerator unit, Galois field multiplication operations of the 2i""th power and the (2i+1)""th power of xcex1 are performed simultaneously. Besides them, it has also two divisor units.
According to a third aspect of the present invention, the apparatus has only one divisor included in the second aspect, so that such control is conducted, for example, that according to values taken on by these two error-position polynomial arithmetic units, an input may be appropriately selected in using of the divisor, that, as necessary, the clock signal may be started or stopped or eventually the next calculation of a denominator and a numerator may be stopped until division is terminated, and that a state value of the register may be held. Further, to the processing unit on the downstream side is output a signal indicating which input has been selected.
Actually, however, the error rate is low, error correction operations are further accelerated.
Also, sharing of various functions is expected to reduce the area and space for arranging the circuits.
According to a fourth aspect of the present invention, same as the first aspect according to claim 1, the selector and the memory unit are each provided one but, unlike it, the arithmetic unit of the Galois field multiplier unit is provided three or more and, correspondingly, the full adder is also provided many. With this, as mentioned above, the actual error rate is low, thus further accelerating chien""s searching operations.
The apparatus according to a fifth aspect of the present invention has the same actions and effects on the fourth aspect as those the second aspect has on the first aspect. Also, correspondingly, as compared to the second aspect according to claim 2 of the present invention, this aspect has many calculating units and so is complicated, providing various necessary control and signal outputs though.
The apparatus according to a sixth aspect of the present invention has the same actions on the fifth aspect as those the third aspect has on the second aspect. Also, correspondingly, as compared to the third aspect, this aspect has many calculating units and so is complicated, providing various necessary control and signal output though.
According to a seventh aspect of the present invention, when the summing unit of every error-position calculating unit in a plurality of error-position calculating units comes up with 0, the divisor is rendered inoperative, thus saving on power dissipation.
According to eighth and ninth aspects of the present invention, if the number of the solutions (roots) of an error-position polynomial becomes the same as the order of this equation in the first through seventh aspects, the process for obtaining the solutions of the following equations is stopped, thus further speeding chien""s searching operations.